package lianbiao;

/**
 * @Author Stringzhua
 * @Date 2025/10/23 14:51
 * description:单链表
 */
public class SinglyLinkedList {
    // 链表节点内部类
    static class Node {
        String data;  // 节点存储的数据（使用String类型，与Python示例一致）
        Node next;    // 指向下一个节点的引用

        // 节点构造方法
        public Node(String data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node head;  // 链表头节点

    // 单链表构造方法
    public SinglyLinkedList() {
        this.head = null;
    }

    /**
     * 尾部添加节点（尾插法）
     * @param data 插入的数据
     */
    public void append(String data) {
        Node newNode = new Node(data);

        // 如果链表为空，将新节点设为头节点
        if (head == null) {
            head = newNode;
            return;
        }

        // 遍历到链表末尾
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        // 将新节点链接到末尾
        current.next = newNode;
    }

    /**
     * 头部添加节点（头插法）
     * @param data 插入的数据
     */
    public void prepend(String data) {
        Node newNode = new Node(data);
        // 将新节点的next指向当前的头节点
        newNode.next = head;
        // 更新头节点为新节点
        head = newNode;
    }

    /**
     * 在指定节点后添加新节点
     * @param prevNode 指定的前一个节点
     * @param data 插入的数据
     */
    public void insertAfterNode(Node prevNode, String data) {
        // 检查前一个节点是否存在
        if (prevNode == null) {
            System.out.println("前一个节点不存在");
            return;
        }

        Node newNode = new Node(data);
        // 将新节点的next指向前一个节点的next
        newNode.next = prevNode.next;
        // 将前一个节点的next指向新节点
        prevNode.next = newNode;
    }

    /**
     * 删除包含特定值的节点
     * @param key 要删除的节点值
     */
    public void deleteNode(String key) {
        // 保存当前节点
        Node current = head;

        // 如果头节点包含要删除的值
        if (current != null && current.data.equals(key)) {
            head = current.next;
            current = null;
            return;
        }

        // 搜索要删除的节点
        Node prev = null;
        while (current != null && !current.data.equals(key)) {
            prev = current;
            current = current.next;
        }

        // 如果没有找到要删除的节点
        if (current == null) {
            return;
        }

        // 将前一个节点的next跳过当前节点指向下一个节点
        prev.next = current.next;
        current = null;
    }

    /**
     * 按位置删除节点
     * @param position 要删除的节点位置（从0开始）
     */
    public void deleteAtPos(int position) {
        if (head == null) {
            return;
        }

        // 如果删除头节点
        if (position == 0) {
            head = head.next;
            return;
        }

        Node current = head;
        for (int i = 0; i < position - 1; i++) {
            if (current == null || current.next == null) {
                return;
            }
            current = current.next;
        }

        // 如果到达链表末尾
        if (current == null || current.next == null) {
            return;
        }

        // 删除current.next节点
        Node nextNode = current.next.next;
        current.next = nextNode;
    }

    /**
     * 查找包含特定值的节点
     * @param key 要查找的值
     * @return 是否找到
     */
    public boolean search(String key) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(key)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 更新节点值
     * @param key 要更新的旧值
     * @param newData 新值
     * @return 是否更新成功
     */
    public boolean updateNode(String key, String newData) {
        Node current = head;
        while (current != null) {
            if (current.data.equals(key)) {
                current.data = newData;
                return true;
            }
            current = current.next;
        }
        return false;
    }

    /**
     * 打印链表
     */
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // 创建一个空链表
        SinglyLinkedList linkedList = new SinglyLinkedList();

        // 在末尾添加节点
        linkedList.append("A");
        linkedList.append("B");
        linkedList.append("C");

        System.out.println("原始链表:");
        linkedList.printList();  // 输出: A -> B -> C -> null

        // 在头部添加节点
        linkedList.prepend("X");
        System.out.println("在头部添加 'X' 后:");
        linkedList.printList();  // 输出: X -> A -> B -> C -> null

        // 在 'A' 后添加节点
        Node current = linkedList.head.next;  // 'A' 节点
        linkedList.insertAfterNode(current, "Y");
        System.out.println("在 'A' 后添加 'Y' 后:");
        linkedList.printList();  // 输出: X -> A -> Y -> B -> C -> null

        // 删除值为 'B' 的节点
        linkedList.deleteNode("B");
        System.out.println("删除值为 'B' 的节点后:");
        linkedList.printList();  // 输出: X -> A -> Y -> C -> null

        // 查找值为 'Y' 的节点
        System.out.println("查找值为 'Y' 的节点: " + linkedList.search("Y"));  // 输出: true
        System.out.println("查找值为 'B' 的节点: " + linkedList.search("B"));  // 输出: false

        // 更新值为 'Y' 的节点为 'Z'
        linkedList.updateNode("Y", "Z");
        System.out.println("更新值为 'Y' 的节点为 'Z' 后:");
        linkedList.printList();  // 输出: X -> A -> Z -> C -> null
    }
}